3.1_循环群与对称群_循环群与初等数论.1.ZH解释

本章节的标题指出了核心内容：循环群和对称群。这是群论中两类非常基本且重要的群。

• 循环群：结构最简单的群之一，由单个元素通过群运算反复作用于自身而生成。它们是理解更复杂群结构的基石。
• 对称群：研究的是一个集合上所有双射（置换）构成的群，它在几何、组合学以及伽罗瓦理论中都有着深刻的应用。

本章将深入探讨这两类群的性质、结构以及它们之间的联系。

本节的标题揭示了循环群和初等数论之间的深刻联系。

• 循环群的研究，特别是有限循环群，其结构和性质（如元素的阶、子群的结构）可以完全通过整数的算术性质来描述。
• 初等数论是研究整数性质的数学分支，核心概念包括整除、素数、同余等。

本节将展示，对整数同余类群 $\mathbb{Z}/n\mathbb{Z}$ 的研究，实际上就是循环群理论的一个核心模型，而数论中的许多经典结果，如带余除法、最大公约数和算术基本定理，都是理解循环群性质的关键工具。

这部分是引言，旨在说明循环群理论与初等数论的紧密关系。

• “循环群的故事”：这是一种拟人化的说法，表明循环群的理论体系和发展历史。
• “与初等数论……密切相关”：明确指出理解循环群离不开数论中的基本概念，如因式分解（将一个整数写成若干整数的乘积）、素数（只能被1和自身整除的正整数）和同余（两个整数除以同一个正整数所得余数相同）。
• “从‘第一原理’证明”：意味着证明将不依赖于更高级的理论，而是基于最基本的公理或已被接受的简单事实，这里特指自然数集 $\mathbb{N}$ 的加法、乘法和序（大小关系）。
• “最基本的事实之一”：引出即将介绍的带余数长除法定理，强调其在整个理论体系中的基础性地位。

这个定理是欧几里得除法的正式表述，是数论的基石。

• “设 $n \in \mathbb{N}$”：规定除数 $n$ 是一个自然数，即一个正整数 ($1, 2, 3, \ldots$)。
• “对于所有的 $a \in \mathbb{Z}$”：规定被除数 $a$ 可以是任何整数，包括正数、负数和零。
• “存在唯一的整数 $q$ 和 $r$”：这是定理的核心结论，包含两部分：

1. 存在性：总能找到这样一对整数 $q$ 和 $r$。
2. 唯一性：满足条件的这样一对整数 $q$ 和 $r$ 是独一无二的。
   • “$0 \leq r \leq n-1$”：这是对余数 $r$ 的关键约束。它必须是非负的，并且严格小于除数 $n$。这个条件保证了唯一性。
   • “$a=n q+r$”：这是除法关系的核心等式。被除数 $a$ 等于除数 $n$ 乘以商 $q$ 再加上余数 $r$。

这部分是证明定理的存在性，即证明对于任意的 $a$ 和 $n$，总能找到符合条件的 $q$ 和 $r$。证明过程非常精巧，依赖于良序原理。

第一步：构造一个集合 $X$

• 我们定义了一个集合 $X$，它包含了所有形如 $a-nq$ 的数，但有一个前提条件：这个数必须是非负的（$\geq 0$）。
• 直观上，这个集合 $X$ 收集了所有“可能的余数”，但允许它们大于等于 $n$。我们的目标是从这些“可能的余数”中挑出我们真正想要的那个。

第二步：证明 $X$ 不是空集 ($\boldsymbol{X \neq \emptyset}$)

• 这一步是为了确保集合 $X$ 里至少有一个元素，否则后续讨论就没有意义。
• 分两种情况讨论：
• 如果 $a \geq 0$：我们可以让 $q=0$，这样 $a-n(0) = a \geq 0$，所以 $a$ 本身就在集合 $X$ 中。
• 如果 $a < 0$：这里需要一点技巧。取 $q=a$。因为 $a$ 是负数，而 $n$ 是正整数 ($n \geq 1$)，所以 $-na$ 是一个正数。表达式 $a-na = a(1-n)$。由于 $a<0$ 且 $1-n \leq 0$，所以 $a(1-n) \geq 0$。因此 $a-na$ 也在集合 $X$ 中。
• 结论：无论 $a$ 是什么整数，集合 $X$ 都不是空的。

第三步：找到 $X$ 中的最小元素

• 集合 $X$ 的所有元素都是非负整数。
• 良序原理：任何非空的自然数子集（或非负整数子集）必定有一个最小元素。
• 因为我们已经证明了 $X$ 是一个非空的非负整数集合，所以根据良序原理，它必然存在一个最小的元素。我们把这个最小元素命名为 $r$。

第四步：证明这个最小元素 $r$ 就是我们想要的余数

• 根据 $r$ 的来源（它在集合 $X$ 中），我们知道 $r$ 的形式是 $r = a - nq$ (对于某个特定的整数 $q$)，并且 $r \geq 0$。
• 将 $r = a - nq$ 变形，就得到 $a = nq + r$。这已经满足了等式要求和余数非负的要求。
• 现在只剩下最后一步，也是最关键的一步：证明 $r \leq n-1$（等价于 $r < n$）。

第五步：使用反证法证明 $r < n$

• 假设我们得到的最小元素 $r$ 不满足 $r < n$，也就是说，假设 $r \geq n$。
• 基于这个假设，我们来构造一个新的数：$r' = r - n$。
• 因为 $r \geq n$，所以 $r' = r - n \geq 0$。这说明 $r'$ 也是一个非负数。
• 同时，因为 $n$ 是正整数，所以 $r' = r - n < r$。这说明我们找到了一个比 $r$ 更小的数。
• 接下来看 $r'$ 是否在集合 $X$ 中。

$r' = r - n = (a - nq) - n = a - n(q+1)$。

这个形式是 $a - n \times (\text{一个整数})$，并且我们已经知道它是非负的。根据集合 $X$ 的定义，$r'$ 必须属于 $X$。

• 矛盾：我们找到了一个元素 $r' \in X$，它比 $r$ 还要小。但这与我们最初定义 $r$ 为 $X$ 中“最小的元素”相矛盾。
• 结论：既然假设导出了矛盾，那么假设本身就是错误的。所以 $r \geq n$ 是不成立的。因此，必然有 $r < n$，即 $r \leq n-1$。

至此，存在性证明完毕。我们成功找到了满足所有条件的 $q$ 和 $r$。

这部分证明定理的唯一性，即满足条件的商和余数是独一无二的。

第一步：设立假设

• 我们假设存在两组不同的商和余数，$(q_1, r_1)$ 和 $(q_2, r_2)$，它们都满足定理的条件。
• 即 $a = nq_1 + r_1$ 和 $a = nq_2 + r_2$，同时 $0 \leq r_1 \leq n-1$ 且 $0 \leq r_2 \leq n-1$。
• 我们的目标是证明，既然它们都成立，那么必然有 $q_1=q_2$ 和 $r_1=r_2$。

第二步：建立关系

• 因为两个表达式都等于 $a$，所以它们彼此相等：

$nq_1 + r_1 = nq_2 + r_2$

• 移项整理，把带 $q$ 的项放在一边，带 $r$ 的项放在另一边：

$r_2 - r_1 = nq_1 - nq_2 = n(q_1 - q_2)$

第三步：分析余数之差的范围

• 我们有两个关于 $r_1$ 和 $r_2$ 的不等式：

$0 \leq r_1 \leq n-1$

$0 \leq r_2 \leq n-1$

• 不失一般性，假设 $r_2 \geq r_1$。（如果 $r_1 > r_2$，交换一下标号即可，不影响结论）。
• 从 $0 \leq r_1$ 两边同时减 $r_1$，得到 $-r_1 \leq 0$。
• 将这个不等式和 $r_2 \leq n-1$ 相加，得到 $r_2 - r_1 \leq n-1$。
• 另外，因为假设了 $r_2 \geq r_1$，所以 $r_2 - r_1 \geq 0$。
• 综合起来，我们得到了关于余数之差 $r_2 - r_1$ 的一个关键范围：

$0 \leq r_2 - r_1 \leq n-1$。

也就是说，这个差值是一个小于 $n$ 的非负整数。

第四步：利用整除性导出矛盾

• 回到第二步的结论：$r_2 - r_1 = n(q_1 - q_2)$。
• 这个等式告诉我们，$r_2 - r_1$ 是 $n$ 的一个倍数。
• 结合第三步的范围，我们现在有两个关于 $r_2 - r_1$ 的信息：

1. 它是一个 $n$ 的倍数。
2. 它是一个在 $[0, n-1]$ 区间内的整数。
   • 在 $0$ 到 $n-1$ 这个范围内，唯一的 $n$ 的倍数是 $0$。（任何正的 $n$ 的倍数，如 $n, 2n, \ldots$，都 $\geq n$，所以不在这个范围内）。
   • 因此，必然有 $r_2 - r_1 = 0$，这意味着 $r_1 = r_2$。

第五步：证明商也相等

• 既然我们已经证明了 $r_1 = r_2$，我们把它代回到 $n(q_1 - q_2) = r_2 - r_1$ 中。
• 得到 $n(q_1 - q_2) = 0$。
• 因为 $n$ 是一个自然数，所以 $n \neq 0$。
• 两个数相乘等于0，其中一个不为0，那么另一个必须为0。
• 所以 $q_1 - q_2 = 0$，这意味着 $q_1 = q_2$。

至此，唯一性证明完毕。我们证明了如果存在两组解，它们必然是同一组解。

这个推论是带余除法定理的第一个直接应用，它描述了同余类集合 $\mathbb{Z}/n\mathbb{Z}$ 的基本结构。

第一步：理解同余类 $[a]_n$

• 同余类 $[a]_n$ 是一个集合，包含了所有与整数 $a$ “模 $n$ 同余”的整数。
• 两个整数 $x$ 和 $y$ 模 $n$ 同余，记作 $x \equiv y \pmod{n}$，意味着它们的差 $x-y$ 是 $n$ 的倍数。
• 所以，$[a]_n = \{x \in \mathbb{Z} \mid x \equiv a \pmod{n} \} = \{a + kn \mid k \in \mathbb{Z} \}$。
• 例如，$[2]_5 = \{\ldots, -8, -3, 2, 7, 12, \ldots\}$。

第二步：为同余类找到一个“标准代表”

• 推论说，对于任何一个同余类 $[a]_n$，我们总能从 $0, 1, \ldots, n-1$ 这个集合中找到一个数 $r$，使得 $[a]_n = [r]_n$。
• 如何找到？ 使用带余除法。对于给定的 $a$，我们知道存在 $q, r$ 使得 $a = nq + r$ 且 $0 \leq r \leq n-1$。
• 从 $a = nq + r$ 移项得到 $a - r = nq$。根据同余的定义，这意味着 $a \equiv r \pmod{n}$。
• 根据同余类的性质，如果 $a \equiv r \pmod{n}$，那么它们的同余类是同一个集合，即 $[a]_n = [r]_n$。
• 这就证明了，任何同余类都可以用一个 $0$到 $n-1$ 之间的整数来表示。

第三步：证明这个“标准代表”是唯一的

• 假设有两个在 $0$ 到 $n-1$ 之间的数 $r_1$ 和 $r_2$，它们代表了同一个同余类，即 $[r_1]_n = [r_2]_n$。
• 我们需要证明 $r_1$ 必须等于 $r_2$。
• $[r_1]_n = [r_2]_n$ 意味着 $r_1 \equiv r_2 \pmod{n}$，也就是说 $r_1 - r_2$ 是 $n$ 的倍数。
• 但是我们知道 $0 \leq r_1 \leq n-1$ 且 $0 \leq r_2 \leq n-1$。
• 这意味着它们的差 $r_1 - r_2$ 的范围是 $-(n-1) \leq r_1 - r_2 \leq n-1$。
• 在 $-(n-1)$ 到 $n-1$ 这个区间内，唯一的 $n$ 的倍数是 $0$。
• 所以 $r_1 - r_2 = 0$，即 $r_1 = r_2$。
• 这证明了在 $0, 1, \ldots, n-1$ 中，能代表给定同余类的元素是唯一的。

第四步：结论

• 既然每个同余类都与 $0, 1, \ldots, n-1$ 中的一个数唯一对应，那么不同的数 $r_1, r_2$ (都在这个范围内) 必然对应不同的同余类 $[r_1]_n, [r_2]_n$。
• 这意味着同余类的总数恰好就是 $0, 1, \ldots, n-1$ 这些代表元的数量，即 $n$ 个。
• 因此，集合 $\mathbb{Z}/n\mathbb{Z}$ (所有不同同余类的集合) 的元素个数是 $n$，并且可以明确地写成 $\{[0]_n, [1]_n, \ldots, [n-1]_n\}$。

这个推论将带余除法的思想应用到了一个抽象的群元素上，用来判断一个元素的任意整数次幂何时等于单位元。

第一步：理解元素的阶

• 一个群元素 $g$ 的阶 (order)，记作 $o(g)$，是使得 $g^n=1$（其中1是群的单位元）的最小正整数 $n$。
• “阶为 $n$” 意味着：

1. $g^n = 1$。
2. 对于任何正整数 $k < n$，都有 $g^k \neq 1$。

第二步：证明 “$\boldsymbol{\Leftarrow}$” (如果 $n \mid N$，那么 $g^N=1$)

• 这是比较直接的一半。
• $n \mid N$ 表示 $N$ 是 $n$ 的倍数，即存在一个整数 $k$ 使得 $N=nk$。
• 我们来计算 $g^N$：

$g^N = g^{nk} = (g^n)^k$

• 因为 $g$ 的阶是 $n$，所以我们知道 $g^n=1$。
• 代入上式：$g^N = (1)^k = 1$。
• 证明完毕。

第三步：证明 “$\boldsymbol{\Rightarrow}$” (如果 $g^N=1$，那么 $n \mid N$)

• 这是更关键的一半，需要用到带余除法。
• 假设 $g^N=1$。我们想证明 $N$ 必须是 $n$ 的倍数。
• 对整数 $N$ 和阶 $n$ 应用带余除法：存在唯一的整数 $q$ 和 $r$ 使得 $N = nq + r$，其中 $0 \leq r \leq n-1$。
• 我们来计算 $g^N$ 的另一种方式：

$g^N = g^{nq+r} = g^{nq} \cdot g^r = (g^n)^q \cdot g^r$

• 同样，因为 $g^n=1$，所以 $(g^n)^q = 1^q = 1$。
• 于是 $g^N = 1 \cdot g^r = g^r$。
• 现在我们有两个关于 $g^N$ 的表达式：一个是我们的假设 $g^N=1$，另一个是我们的推导 $g^N=g^r$。
• 因此，我们得到 $g^r=1$。

第四步：利用阶的定义得出结论

• 我们得到了 $g^r=1$，并且我们知道 $r$ 的范围是 $0 \leq r \leq n-1$。
• 回顾阶的定义：$n$ 是使得 $g^k=1$ 的 最小正整数。
• 这意味着如果有一个非负整数 $r < n$ 使得 $g^r=1$，那么这个 $r$ 只能是 $0$。（因为如果 $r>0$，就与 $n$ 是最小的那个正整数矛盾了）。
• 所以，我们必须有 $r=0$。
• 将 $r=0$ 代回到带余除法的等式中：$N = nq + 0 = nq$。
• 这表明 $N$ 是 $n$ 的倍数，即 $n \mid N$。
• 证明完毕。

这部分是对推论1.1.3的重要性的阐述，它揭示了所有有限循环群的普适结构。

第一步：$\langle g\rangle \cong \mathbb{Z} / n \mathbb{Z}$

• $\langle g \rangle$: 由元素 $g$ 生成的循环子群，即集合 $\{ \ldots, g^{-2}, g^{-1}, g^0, g^1, g^2, \ldots \}$。
• $\mathbb{Z}/n\mathbb{Z}$: 模 $n$ 整数加法群，其元素是 $\{[0]_n, [1]_n, \ldots, [n-1]_n\}$。
• $\cong$: 同构符号，表示两个群在结构上是完全一样的，只是元素的名字不同。
• 为什么同构？
• 我们可以建立一个映射 $f: \mathbb{Z}/n\mathbb{Z} \to \langle g \rangle$，定义为 $f([k]_n) = g^k$。
• 这个映射是良定义的吗？ 即如果 $[k_1]_n = [k_2]_n$，那么 $f([k_1]_n)$ 是否等于 $f([k_2]_n)$？
• $[k_1]_n = [k_2]_n \implies k_1 \equiv k_2 \pmod n \implies k_1 - k_2 = qn$。
• $g^{k_1} = g^{k_2+qn} = g^{k_2} \cdot (g^n)^q = g^{k_2} \cdot 1^q = g^{k_2}$。
• 所以 $f([k_1]_n) = f([k_2]_n)$。映射是良定义的。
• 这个映射是同态吗？ 即 $f([k_1]_n + [k_2]_n)$ 是否等于 $f([k_1]_n) \cdot f([k_2]_n)$？（左边是 $\mathbb{Z}/n\mathbb{Z}$ 的加法，右边是 $\langle g \rangle$ 的乘法）
• $f([k_1]_n + [k_2]_n) = f([k_1+k_2]_n) = g^{k_1+k_2}$。
• $f([k_1]_n) \cdot f([k_2]_n) = g^{k_1} \cdot g^{k_2}$。
• 两者相等，所以是同态。
• 这个映射是双射吗？
• 满射：$\langle g \rangle$ 中的任何元素都可以写成 $g^k$ 的形式，它正好是 $[k]_n$ 的像。所以是满射。
• 单射：如果 $f([k_1]_n) = f([k_2]_n)$，即 $g^{k_1} = g^{k_2}$，那么 $g^{k_1-k_2}=1$。根据推论1.1.3，这意味着 $n \mid (k_1-k_2)$，即 $k_1 \equiv k_2 \pmod n$，所以 $[k_1]_n = [k_2]_n$。所以是单射。
• 既然映射 $f$ 是一个同态也是一个双射，那么它就是一个同构。

第二步：唯一的同构

• “存在一个唯一的同构 ... 使得 $f([1]_n) = g$”：
• $[1]_n$ 是 $\mathbb{Z}/n\mathbb{Z}$ 的一个生成元。$g$ 是 $\langle g \rangle$ 的生成元。
• 一个循环群的同构完全由它如何映射生成元来决定。一旦我们规定了 $f([1]_n) = g$，那么对于任何 $[k]_n$，

$f([k]_n) = f([1]_n + \ldots + [1]_n) = f([1]_n) \cdot \ldots \cdot f([1]_n) = g^k$。

• 映射的方式就被完全定死了，因此这个同构是唯一的。

第三步：元素的唯一表示

• “$\langle g\rangle$的每个元素都可以唯一地写成$g^{r}, 0 \leq r \leq n-1$。”
• 存在性：$\langle g \rangle$ 中的任何元素都是 $g^k$ 的形式。对 $k$ 进行带余除法，$k = nq+r$，$0 \leq r \leq n-1$。于是 $g^k = g^{nq+r} = (g^n)^q g^r = 1^q g^r = g^r$。所以任何元素都可以表示成这种形式。
• 唯一性：如果 $g^{r_1} = g^{r_2}$，其中 $0 \leq r_1, r_2 \leq n-1$。那么 $g^{r_1-r_2}=1$。根据推论1.1.3，$n \mid (r_1-r_2)$。但是 $-(n-1) \leq r_1-r_2 \leq n-1$，在这个范围内唯一的 $n$ 的倍数是0。所以 $r_1-r_2=0$，即 $r_1=r_2$。

第四步：群的阶

• “因此 $\#(\langle g\rangle)=n$。”
• 既然 $\langle g \rangle$ 的元素与集合 $\{g^0, g^1, \ldots, g^{n-1}\}$ 是一一对应的，那么 $\langle g \rangle$ 的元素个数就是这个集合的元素个数，即 $n$ 个。
• 结论：元素的阶等于它生成的循环子群的阶。

这个推论是循环群的完全分类定理。它极其简洁地告诉我们，世界上所有的循环群，无论其元素是什么，其具体运算是什么，从抽象结构的角度看，只有两种可能。

第一步：什么是循环群？

• 一个群 $G$ 如果能由它的某一个元素 $g$ 生成，即 $G = \langle g \rangle$，那么 $G$ 就是一个循环群。

第二步：分情况讨论生成元的阶

• 生成元 $g$ 的阶有两种可能性：

1. 无限阶: 对于任何正整数 $k$，$g^k \neq 1$。
2. 有限阶: 存在一个最小的正整数 $n$ 使得 $g^n=1$。

第三步：情况一：$g$ 是无限阶

• 如果 $g$ 是无限阶，那么它生成的群 $\langle g \rangle = \{\ldots, g^{-2}, g^{-1}, g^0, g^1, g^2, \ldots\}$ 中的所有元素 $g^k$ 都是互不相同的。（如果 $g^{k_1}=g^{k_2}$ 且 $k_1 \neq k_2$，那么 $g^{k_1-k_2}=1$，这与无限阶矛盾）。
• 考虑整数加法群 $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$。
• 我们可以建立一个映射 $f: \mathbb{Z} \to \langle g \rangle$，定义为 $f(k) = g^k$。
• 这个映射是一个同构（双射的同态），证明过程与推论1.1.3的讨论类似。
• 因此，任何由无限阶元素生成的循环群都同构于 $\mathbb{Z}$。

第四步：情况二：$g$ 是有限阶

• 假设 $g$ 的阶是 $n$。
• 根据推论1.1.3之后的那段讨论，我们已经详细证明了，在这种情况下，$\langle g \rangle$ 同构于 $\mathbb{Z}/n\mathbb{Z}$。

第五步：总结

• 既然任何一个循环群 $G = \langle g \rangle$ 的生成元 $g$ 要么是无限阶，要么是有限阶 $n$。
• 并且这两种情况分别对应于同构于 $\mathbb{Z}$ 和 $\mathbb{Z}/n\mathbb{Z}$。
• 那么结论就是：任何一个循环群，必然同构于 $\mathbb{Z}$ 或 $\mathbb{Z}/n\mathbb{Z}$ 之一。

这部分承上启下，明确了接下来学习的策略。

• “从现在开始，我们将专注于群 $\mathbb{Z}$ 和 $\mathbb{Z}/n\mathbb{Z}$”：这是一个战略宣告。因为推论 1.1.4 已经证明了这两个群是所有循环群的“原型”或“模型”，所以研究它们就等于研究了所有循环群。
• “任何对 $\mathbb{Z}$ 或 $\mathbb{Z}/n\mathbb{Z}$ 证明的代数结果”：这里指的“代数结果”是那些只依赖于群运算结构的性质，例如：
• 一个群有多少个子群？
• 每个子群是什么样的？它们是循环的吗？它们的生成元是什么？
• 群里每个元素的阶是多少？
• 有多少个生成元？
• “都将对任意循环群具有自然的类比”：这意味着，如果我们证明了 $\mathbb{Z}/12\mathbb{Z}$ 有一个4阶的子群，那么任何一个12阶循环群（比如12次旋转群）也必然有一个4阶的子群。这种性质的“转移”或“翻译”是通过同构来保证的。

这个命题描述了整数加法群 $\mathbb{Z}$ 的一个非常优美的性质：它的所有子群结构都非常简单，都是循环群。

证明思路：

这个证明再次精妙地使用了良序原理。

第一步：处理平凡情况

• 考虑 $\mathbb{Z}$ 的一个子群 $H$。
• 如果 $H$ 只包含一个元素，那么这个元素必须是单位元，即 $0$。所以 $H=\{0\}$。
• 集合 $\{0\}$ 可以由 $0$ 生成，即 $H = \langle 0 \rangle$。根据定义，它是一个循环群。

第二步：处理非平凡情况

• 假设 $H$ 不是平凡子群 $\{0\}$，即 $H$ 中至少包含一个非零元素 $a$。
• 因为 $H$ 是一个子群，如果 $a \in H$，那么它的逆元 $-a$ 也必须在 $H$ 中。
• যেহেতু $a \neq 0$，那么 $a$ 和 $-a$ 中必然有一个是正数。
• 这意味着 $H$ 中至少包含一个正整数。

第三步：找到最小正元素

• 考虑集合 $H \cap \mathbb{N}$，也就是 $H$ 中所有正整数的集合。
• 根据第二步，这个集合是非空的。
• 根据良序原理（任何非空正整数集合都有一个最小元素），$H \cap \mathbb{N}$ 必然存在一个最小的元素。我们把这个元素命名为 $d$。

第四步：证明 $H = \langle d \rangle$

• 我们需要证明子群 $H$ 和由 $d$ 生成的循环群 $\langle d \rangle$ 是同一个集合。这需要证明两个方向的包含关系：

1. 证明 $\langle d \rangle \subseteq H$:
   • $\langle d \rangle$ 的定义是 $\{kd \mid k \in \mathbb{Z}\}$，即所有 $d$ 的整数倍。
   • 我们知道 $d$ 是从 $H$ 中选出来的，所以 $d \in H$。
   • 因为 $H$ 是一个子群，它对加法和取逆元是封闭的。所以 $d+d=2d \in H$, $d+d+d=3d \in H$, ... 任何正数倍 $kd$ 都在 $H$ 中。
   • 同样，单位元 $0d=0 \in H$，逆元 $-d \in H$, $-2d \in H$, ...
   • 因此，所有 $d$ 的整数倍都在 $H$ 中，即 $\langle d \rangle \subseteq H$。
2. 证明 $H \subseteq \langle d \rangle$ (关键步骤):
   • 我们需要证明 $H$ 中的任何一个元素 $a$，都必然是 $d$ 的倍数。
   • 对任意的 $a \in H$，我们使用带余除法，用 $d$ 去除 $a$。
   • 存在唯一的 $q, r$ 使得 $a = dq + r$，其中 $0 \leq r \leq d-1$。
   • 我们的目标是证明 $r$ 必须等于 $0$。
   • 从等式中移项，得到 $r = a - dq$。
   • 现在分析 $r$ 的归属：
   • $a$ 是我们从 $H$ 中任意取的一个元素，所以 $a \in H$。
   • $d \in H$，我们已经证明了 $\langle d \rangle \subseteq H$，所以 $d$ 的任何整数倍 $dq$ 也都在 $H$ 中。
   • 因为 $H$ 是一个子群，它对减法（加法和取逆的组合）是封闭的，所以 $r = a - dq$ 也必须在 $H$ 中。
   • 现在我们知道了关于 $r$ 的两件事：
   • $r \in H$。
   • $0 \leq r \leq d-1$。
   • 回忆一下 $d$ 是什么？$d$ 是 $H$ 中“最小的 正 元素”。
   • 如果 $r > 0$，那么 $r$ 将是一个 $H$ 中的正元素，并且 $r < d$。但这与 $d$ 是最小的那个正元素相矛盾。
   • 因此，唯一的可能性就是 $r$ 不能是正数，即 $r=0$。
   • 如果 $r=0$，那么 $a = dq + 0 = dq$。这表明 $a$ 是 $d$ 的一个倍数，所以 $a \in \langle d \rangle$。
   • 因为 $a$ 是 $H$ 中任意一个元素，所以我们证明了 $H$ 中的所有元素都在 $\langle d \rangle$ 中，即 $H \subseteq \langle d \rangle$。

第五步：结论

• 既然 $\langle d \rangle \subseteq H$ 且 $H \subseteq \langle d \rangle$，那么 $H = \langle d \rangle$。
• 这证明了任何一个 $\mathbb{Z}$ 的非平凡子群都是由它自己的最小正元素生成的循环群。
• 结合平凡情况，我们得出结论：$\mathbb{Z}$ 的每个子群都是循环的。

这个备注是对命题1.1.5证明过程的进一步解读和引申。

• “如果$H \leq \mathbb{Z}$不是平凡子群$\{0\}$”：我们只考虑那些至少包含一个非零元素的子群。
• “那么$H=\langle d\rangle$”：这是命题1.1.5的结论，其中 $d$ 是 $H$ 中最小的正元素。
• “$H$本身是一个无限循环群”：
• 因为 $d$ 是一个正整数，所以它在加法群 $\mathbb{Z}$ 中的阶是无限的（不存在正整数 $k$ 使得 $k \cdot d = 0$）。
• 根据推论1.1.4的分类，由一个无限阶元素生成的循环群是无限循环群。
• “因此$H \cong \mathbb{Z}$”：
• 再次根据推论1.1.4，任何无限循环群都同构于整数加法群 $\mathbb{Z}$。
• 这揭示了一个深刻的事实：$\mathbb{Z}$ 的任何非平凡子群，在结构上都和 $\mathbb{Z}$ 本身一模一样！例如，偶数群 $(\{2k\}, +)$ 和整数群 $(\mathbb{Z}, +)$ 是同构的，一个同构映射是 $f(k) = 2k$。
• “并且$H$的两个生成元是$\pm d$”：
• 我们已经知道 $d$ 是 $H$ 的一个生成元，因为 $H=\langle d\rangle$。
• 一个循环群 $\langle g \rangle$ 的另一个生成元是它的逆元 $g^{-1}$ (当且仅当阶大于2)。在加法群中，$d$ 的逆元是 $-d$。
• 我们需要验证 $\langle -d \rangle$ 是否也等于 $H$。
• $\langle -d \rangle = \{k(-d) \mid k \in \mathbb{Z}\} = \{(-k)d \mid k \in \mathbb{Z}\}$。
• 因为当 $k$ 取遍所有整数时，$-k$ 也取遍所有整数。所以 $\{(-k)d \mid k \in \mathbb{Z}\}$ 和 $\{k'd \mid k' \in \mathbb{Z}\}$ 是同一个集合。
• 因此 $\langle -d \rangle = \langle d \rangle = H$。
• 所以，$d$ 和 $-d$ 都是 $H$ 的生成元。事实上，它们是唯二的生成元。

这个命题将命题1.1.5的结论推广到了有限循环群的原型 $\mathbb{Z}/n\mathbb{Z}$ 上。它断言，$\mathbb{Z}/n\mathbb{Z}$ 的所有子群也都是循环的。

证明思路:

证明的逻辑与命题1.1.5的证明高度相似，但操作对象从整数变成了同余类，并且利用了集合的有限性，而不再需要良序原理。

第一步：构造一个代表元集合 $X$

• 设 $H$ 是 $\mathbb{Z}/n\mathbb{Z}$ 的一个子群。$H$ 的元素是形如 $[a]_n$ 的同余类。
• 我们构造一个普通的整数集合 $X$，这个集合包含了 $H$ 中所有同余类的最小非负代表元。
• $X = \{r \in \mathbb{Z} \mid 0 \leq r \leq n-1 \text{ 且 } [r]_n \in H \}$
• 这个集合 $X$ 是一个在 $0$ 到 $n-1$ 之间的整数集合，所以它是一个有限集。

第二步：找到 $X$ 中的最小元素 $d$

• 因为 $H$ 是一个子群，所以它至少包含单位元 $[0]_n$。这意味着 $0 \in X$。所以 $X$ 非空。
• 既然 $X$ 是一个非空的有限整数集，它必然有一个最小元素。我们称之为 $d$。（注意：这里原文的证明逻辑可以更简化，因为 $X$ 是有限的，直接找最小元素即可，不一定需要像证明中那样复杂。但原文的思路是为了和前面保持一致）。
• 这个 $d$ 具有两个性质：

1. $d$ 是 $X$ 中最小的元素。（在 $H$ 的所有最小非负代表元中， $d$ 是最小的那个非零值，如果 $H$ 非平凡的话）。
2. $[d]_n$ 是 $H$ 的一个元素。

第三步：证明 $H = \langle [d]_n \rangle$

• 同样，我们需要证明两个方向的包含关系。

1. $\langle [d]_n \rangle \subseteq H$:
   • 因为 $[d]_n \in H$，而 $H$ 是一个子群，对群运算（加法）封闭。
   • 所以 $[d]_n$ 的所有倍数（如 $k \cdot [d]_n = [kd]_n$）都必须在 $H$ 中。
   • 因此，由 $[d]_n$ 生成的循环子群 $\langle [d]_n \rangle$ 整个都包含在 $H$ 中。
2. $H \subseteq \langle [d]_n \rangle$ (关键步骤):
   • 取 $H$ 中任意一个元素 $[k]_n$。
   • 我们对整数 $k$ 和我们找到的那个 $d$ 应用带余除法。
   • 存在唯一的 $q, s$ 使得 $k = dq + s$，其中 $0 \leq s \leq d-1$。
   • 现在我们把这个关系转换到同余类中：
   • 移项得到：$[s]_n = [k]_n - q \cdot [d]_n$。
   • 分析 $[s]_n$ 的归属：
   • 我们是从 $H$ 中取的 $[k]_n$，所以 $[k]_n \in H$。
   • 我们知道 $[d]_n \in H$，所以它的倍数 $q \cdot [d]_n$ 也在 $H$ 中。
   • 因为 $H$ 是子群，对减法封闭，所以 $[s]_n = [k]_n - q \cdot [d]_n$ 也在 $H$ 中。
   • 现在我们知道了关于 $s$ 的两件事：
   • $[s]_n \in H$。
   • $0 \leq s \leq d-1$。
   • 因为 $[s]_n \in H$ 且 $0 \leq s \leq n-1$ (因为 $s < d \le n-1$)，根据集合 $X$ 的定义，整数 $s$ 必须在集合 $X$ 中。
   • 但是 $d$ 是 $X$ 中 最小的非零元素（如果H非平凡），而 $s < d$。如果 $s>0$ 就会产生矛盾。
   • 因此，唯一的可能性是 $s=0$。
   • 如果 $s=0$，那么 $k = dq$。在同余类中就是 $[k]_n = [dq]_n = q \cdot [d]_n$。
   • 这表明 $[k]_n$ 是 $[d]_n$ 的一个倍数，所以 $[k]_n \in \langle [d]_n \rangle$。
   • 因为 $[k]_n$ 是 $H$ 中任意一个元素，所以我们证明了 $H \subseteq \langle [d]_n \rangle$。

第四步：结论

• 既然 $\langle [d]_n \rangle \subseteq H$ 且 $H \subseteq \langle [d]_n \rangle$，那么 $H = \langle [d]_n \rangle$。
• 这证明了 $\mathbb{Z}/n\mathbb{Z}$ 的任何一个子群都是由它的某一个元素生成的循环群。

这个推论是前面所有工作的顶峰，给出了关于循环群的一个最基本和最重要的性质。

第一步：陈述结论

• 结论: 任何一个循环群的任何一个子群，其本身也必然是一个循环群。

第二步：证明策略

• 证明不再需要从头开始，而是巧妙地利用已经建立的三个基石：

1. 循环群分类定理 (推论 1.1.4): 任何循环群 $G$ 要么同构于 $\mathbb{Z}$，要么同构于 $\mathbb{Z}/n\mathbb{Z}$。
2. $\mathbb{Z}$ 的子群结构 (命题 1.1.5): $\mathbb{Z}$ 的所有子群都是循环的。
3. $\mathbb{Z}/n\mathbb{Z}$ 的子群结构 (命题 1.1.7): $\mathbb{Z}/n\mathbb{Z}$ 的所有子群都是循环的。

第三步：论证过程

• 设 $G$ 是一个任意的循环群，设 $H$ 是 $G$ 的一个任意子群。我们想证明 $H$ 是循环的。
• 根据分类定理，存在一个同构 $f: G \to G'$，其中 $G'$ 要么是 $\mathbb{Z}$，要么是 $\mathbb{Z}/n\mathbb{Z}$。
• 这个同构 $f$ 是一个保持结构不变的双射。
• 原文引用了一个重要性质：在同构映射下，子群的像仍然是子群。也就是说，因为 $H$ 是 $G$ 的子群，所以它的像 $f(H)$ 必然是 $G'$ 的一个子群。
• 现在我们来看 $f(H)$ 是什么。
• 情况一: 如果 $G \cong \mathbb{Z}$，那么 $f(H)$ 是 $\mathbb{Z}$ 的一个子群。根据命题 1.1.5，$\mathbb{Z}$ 的所有子群都是循环的。所以 $f(H)$ 是循环的。
• 情况二: 如果 $G \cong \mathbb{Z}/n\mathbb{Z}$，那么 $f(H)$ 是 $\mathbb{Z}/n\mathbb{Z}$ 的一个子群。根据命题 1.1.7，$\mathbb{Z}/n\mathbb{Z}$ 的所有子群都是循环的。所以 $f(H)$ 也是循环的。
• 在任何情况下，我们都得出了 $f(H)$ 是一个循环子群的结论。
• 原文再次引用一个性质：同构保持循环性。如果 $f(H)$ 是循环的，那么它的原像 $H$ 也必须是循环的。（因为 $f^{-1}$ 也是一个同构，它会把 $f(H)$ 的生成元映射回 $H$ 的生成元）。
• 最终结论: 因此， $H$ 必然是一个循环群。

第四步：对引用的解释

• “$H$是$G_{1}$的子群$\Longleftrightarrow f(H)$是$G_{2}$的子群”：同构映射在子群和子群的像之间建立了一一对应。
• “如果$H=\langle g\rangle$是...循环子群，那么$f(\langle g\rangle)$是...循环子群，事实上它是$\langle f(g)\rangle$”：同构把生成元映成生成元，所以循环群的像还是循环群。
• “$H$是循环的$\Longleftrightarrow f(H)$是循环的”：这是最关键的性质。循环性是一个纯粹的结构性质，因此在同构下保持不变。

这部分是对之前关于 $\mathbb{Z}$ 子群工作的总结，并对接下来关于 $\mathbb{Z}/n\mathbb{Z}$ 子群的研究做出预告。

• “$\mathbb{Z}$的每个子群都可以唯一地描述为$\langle 0\rangle$或$\langle d\rangle$，其中$d>0$”：
• 这是对命题1.1.5及其备注的精确总结。
• 唯一描述: 对于任何一个 $\mathbb{Z}$ 的子群 $H$，都存在一个唯一的非负整数 $d$ 使得 $H=\langle d \rangle$。如果 $H=\{0\}$，则 $d=0$。如果 $H$ 非平凡，则 $d$ 是 $H$ 中最小的正元素。
• 这意味着 $\mathbb{Z}$ 的子群和非负整数之间存在一一对应关系。

• “我们将在后面给出$\mathbb{Z} / n \mathbb{Z}$的子群及其可能的生成元的类似精确描述”：
• 这是一个“剧透”，告诉读者接下来的研究重点。
• 我们已经知道 $\mathbb{Z}/n\mathbb{Z}$ 的子群都是循环的，但我们还想知道更精确的信息：

1. $\mathbb{Z}/n\mathbb{Z}$ 到底有多少个子群？
2. 每个子群的阶是多少？
3. 每个子群的生成元是什么？有多少个生成元？
   • “类似精确描述”暗示了答案可能也和数的整除性质有关。事实也的确如此，$\mathbb{Z}/n\mathbb{Z}$ 的子群与整数 $n$ 的所有正因子之间存在一一对应关系。

本小节的标题“因式分解”点明了主题。在数论中，这通常指将一个整数分解为素数的乘积。但在更广义的代数语境下，它涉及到“整除”这个核心概念。本节将从最基本的整除性质开始，为后续引入最大公约数、互素以及算术基本定理做铺垫。这些数论工具对于精确描述循环群的子群结构和元素阶至关重要。

这部分回顾了整除的定义，并将其与循环群的语言联系起来，然后列举了其基本性质。

定义的等价性:

• $a \mid b$: 读作“a整除b”。这是核心符号。
• $\Longleftrightarrow$存在一个$k \in \mathbb{Z}$使得$b=a k$: 这是整除的代数定义。b可以被表示为a的整数倍。
• $\Longleftrightarrow b$是$a$的倍数**: 这是定义的自然语言描述。
• $\Longleftrightarrow b \in\langle a\rangle$: 这是从循环群的角度来理解。由a生成的循环子群 $\langle a \rangle$ 在加法群 $\mathbb{Z}$ 中就是所有a的倍数的集合 $\{ka \mid k \in \mathbb{Z}\}$。所以b是a的倍数，就等价于b是 $\langle a \rangle$ 中的一个元素。
• $\Longleftrightarrow\langle b\rangle \subseteq\langle a\rangle$: 这是从子群包含关系的角度来理解。如果 $b \in \langle a \rangle$，那么b的所有倍数也必然是a的倍数（因为 $mb = m(ka) = (mk)a$），所以由b生成的子群 $\langle b \rangle$ 包含于由a生成的子群 $\langle a \rangle$。反之，如果 $\langle b \rangle \subseteq \langle a \rangle$，那么 $b$ 本身（即 $1 \cdot b$）必然在 $\langle a \rangle$ 中。这个等价性非常重要，它将数论的整除关系完全翻译成了代数的子群包含关系。

性质解读:

(1) 自反性: $a \mid a$。因为 $a = a \times 1$。

(2) 传递性: $a \mid b$ 意味着 $b=ak_1$。$b \mid c$ 意味着 $c=bk_2$。所以 $c = (ak_1)k_2 = a(k_1k_2)$，因此 $a \mid c$。

(3) 线性组合性质: $a \mid b \implies b=ak_1$，$a \mid c \implies c=ak_2$。那么 $rb+sc = r(ak_1) + s(ak_2) = a(rk_1 + sk_2)$。这是一个整数，所以 $a \mid (rb+sc)$。这意味着如果a能整除几个数，它就能整除这几个数的任何整数线性组合。

(4) 关于0的性质:

• $a \mid 0$：因为 $0 = a \times 0$ 对任何 $a$ 都成立。
• $0 \mid a$：意味着 $a = 0 \times k$。这只有当 $a=0$ 时才可能成立。所以0不能整除任何非零数。

(5) 关于1的性质:

• $1 \mid a$：因为 $a = 1 \times a$ 对任何 $a$ 都成立。
• $a \mid 1$：意味着 $1 = a \times k$。在整数环中，这只有当 $a=1, k=1$ 或 $a=-1, k=-1$ 时才成立。所以能整除1的整数只有 $\pm 1$。

(6) 反对称性 (在模掉符号后): $a \mid b \implies b=ak_1$，$b \mid a \implies a=bk_2$。代入得 $a = (ak_1)k_2 = a(k_1k_2)$。如果 $a \neq 0$，两边消去a得到 $1=k_1k_2$。在整数中，这意味着 $k_1,k_2$ 只能是 $\pm 1$。所以 $b = \pm a$。如果 $a=0$，那么 $b=0k_1=0$，也成立。

这部分给出了最大公约数 (Greatest Common Divisor, GCD) 的严格定义。这个定义比小学里“最大的公共因子”的定义更深刻、更具代数意义。

• 设$a, b \in \mathbb{Z}$，不都为$0$: 前提条件。计算GCD的两个数不能同时为0。如果 $a=b=0$，那么任何数都整除0，没有“最大”的公约数。
• 是一个自然数 $d \in \mathbb{N}$: GCD被定义为一个正整数。
• $d|a$ 且 $d|b$: 这是“公约数”的含义。$d$必须同时整除$a$和$b$。
• 并且，对于所有的$e \in \mathbb{Z}$，如果$e \mid a$且$e \mid b$，那么$e \mid d$: 这是“最大”的真正含义。这里的“最大”不是指数值上的最大，而是指在整除意义下的“最大”。任何其他的公约数 $e$ 都必须能整除 $d$。这说明 $d$ 是所有公约数的倍数。

定义的两个层面:

1. $d$ 是一个公约数。
2. $d$ 是所有公约数的“上级”或“汇合点”。

这个定义比“数值最大的公约数”更强。例如，对于12和18，公约数有 $\pm 1, \pm 2, \pm 3, \pm 6$。数值最大的正公约数是6。我们的定义要求这个 $d=6$ 不仅是数值最大，还必须能被所有其他公约数整除。

• $1 \mid 6$ (√)
• $-1 \mid 6$ (√)
• $2 \mid 6$ (√)
• $-2 \mid 6$ (√)
• $3 \mid 6$ (√)
• $-3 \mid 6$ (√)
• $6 \mid 6$ (√)
• $-6 \mid 6$ (√)

所有公约数都能整除6，所以6符合定义。

这个引理证明，满足定义1.2.1的那个数 $d$ 不可能有两个。

证明思路:

• 这是一个典型的唯一性证明套路：假设有两个，然后证明它们必须相等。
• 假设: 设 $d_1$ 和 $d_2$ 都是 $a$ 和 $b$ 的最大公约数。
• 利用定义:
• 因为 $d_1$ 是一个GCD，而 $d_2$ 是一个公约数（因为它也是一个GCD），根据GCD定义中“最大”的那部分（所有公约数都整除GCD），我们必须有 $d_2 \mid d_1$。
• 同理，因为 $d_2$ 是一个GCD，而 $d_1$ 是一个公约数，我们必须有 $d_1 \mid d_2$。
• 结合整除性质:
• 我们现在得到了两个关系：$d_1 \mid d_2$ 和 $d_2 \mid d_1$。
• 根据前面回顾的整除性的性质(6)，如果两个整数互相整除，那么它们要么相等，要么互为相反数。即 $d_1 = \pm d_2$。
• 利用GCD是自然数的条件:
• 最大公约数的定义规定了它必须是一个自然数，即 $d_1 > 0$ 且 $d_2 > 0$。
• 既然两个数都是正数，那么 $d_1 = \pm d_2$ 中的负号就不可能了。
• 因此，必然有 $d_1 = d_2$。

结论: 最大公约数是唯一的。

这部分对GCD的定义和计算方法进行了补充说明。

(i) 定义的强度

• 这点在强调定义1.2.1中的“整除最大性”比我们通常理解的“数值最大性”要更强。
• “同时整除$a$和$b$的最大的自然数”：这是我们小学就学到的概念。
• “$d$具有定义中更强的性质”：这个更强的性质就是“任何其他公约数都必须整除$d$”。
• 在整数集 $\mathbb{Z}$ 中，这两个定义恰好是等价的。一个正公约数，如果是所有公约数的倍数，那么它在数值上也必然是最大的。反之，数值最大的那个正公约数，也恰好是其他所有公约数的倍数。
• 作者在此处强调这一点，是为了培养一种更抽象的代数思维，因为在其他数学结构中，这两种“最大”可能不一致。

(ii) 计算方法对比

• 小学方法：素因数分解法
• 步骤：

1. 将 $a$ 分解成素数幂的乘积：$a = p_1^{n_1} p_2^{n_2} \cdots$
2. 将 $b$ 分解成素数幂的乘积：$b = p_1^{m_1} p_2^{m_2} \cdots$ (这里的素数基底要取两数的所有素因子之并集，不存在的记为0次幂)
3. $\operatorname{gcd}(a,b)$ 的素因数分解是 $p_1^{\min(n_1, m_1)} p_2^{\min(n_2, m_2)} \cdots$。即对每个素因子，取两者中较小的那个幂次。
   • 缺点：对于非常大的数，$a$ 和 $b$ 的素因数分解本身是一个极其困难的计算问题。现代密码学（如RSA）的安全性就建立在大整数分解的困难性之上。
   • 更高效的方法：
   • 作者预告了存在更高效的方法，即后面要讲的欧几里得算法（辗转相除法）。
   • 这种方法完全不需要进行素因数分解，而是通过一系列的带余除法来快速找到GCD。它的计算效率非常高，即使对于非常大的数也是如此。

这个定理是数论中一个极为重要的结果，通常被称为裴蜀定理或贝祖定理 (Bézout's identity)。它深刻地揭示了最大公约数的代数结构。

(i) 存在性和唯一性

• “最大公约数存在”：这是定理的第一个结论。定义1.2.1只是给出了一个“愿望清单”（如果存在一个数d满足...），但没有保证这样的数一定存在。这个定理的第一部分就弥补了这一点，确认了对于任意不全为0的两个整数a, b，它们的GCD总是存在的。
• “必然是唯一的”：这部分重申了引理1.2.2的结论。

(ii) GCD的线性组合表示

• “存在$n, m \in \mathbb{Z}$使得$d=\operatorname{gcd}(a, b)=a n+b m$”：这是裴蜀定理的核心内容。它说明，$a$ 和 $b$ 的最大公约数 $d$ 不仅仅是一个抽象的数，它总是可以被表示为 $a$ 和 $b$ 的一个整数线性组合。
• 这条性质极为强大，是许多其他数论证明的关键。

(iii) 线性丢番图方程的可解性

• “存在$x, y \in \mathbb{Z}$使得$a x+b y=c \Longleftrightarrow d \mid c$”：这部分给出了形如 $ax+by=c$ 的线性丢番图方程（即求整数解的方程）有解的充要条件。
• 充要条件:
• ($\Rightarrow$) 如果方程 $ax+by=c$ 有整数解 $(x,y)$，那么 $c$ 必须是 $\operatorname{gcd}(a,b)$ 的倍数。

证明：设 $d = \operatorname{gcd}(a,b)$。因为 $d \mid a$ 且 $d \mid b$，根据整除的线性组合性质， $d$ 必然整除它们的任何线性组合，即 $d \mid (ax+by)$。既然 $ax+by=c$，那么 $d \mid c$。

• ($\Leftarrow$) 如果 $c$ 是 $\operatorname{gcd}(a,b)$ 的倍数，那么方程 $ax+by=c$ 必然有整数解。

证明：设 $d = \operatorname{gcd}(a,b)$。如果 $d \mid c$，则存在整数 $k$ 使得 $c=dk$。根据定理的第(ii)部分，存在整数 $n,m$ 使得 $d = an+bm$。将此式两边同乘以 $k$，得到 $dk = (an+bm)k = a(nk) + b(mk)$。令 $x=nk, y=mk$，则 $c = ax+by$。我们找到了方程的一组整数解 $(x,y)$。

这个证明是群论思想在数论中应用的绝佳典范。

第一步：构造一个关键的集合H

• 定义集合 $H$ 为 $a$ 和 $b$ 的所有整数线性组合的集合：$H = \{ax+by \mid x,y \in \mathbb{Z}\}$。
• 这个集合 $H$ 正是定理(iii)中方程左边的所有可能取值。

第二步：证明H是$\mathbb{Z}$的子群

• 这是一个标准的子群验证过程：

1. 闭合性: 取 $H$ 中任意两个元素 $h_1 = ax_1+by_1$ 和 $h_2=ax_2+by_2$。它们的和 $h_1+h_2 = a(x_1+x_2) + b(y_1+y_2)$。因为 $x_1+x_2$ 和 $y_1+y_2$ 仍然是整数，所以和的形式仍然是 $a(\text{int})+b(\text{int})$，故仍在 $H$ 中。
2. 单位元: $0 = a(0)+b(0)$。取 $x=0, y=0$ 即可得到单位元0，所以 $0 \in H$。
3. 逆元: 取 $H$ 中任意一个元素 $h = ax+by$。它的加法逆元是 $-h = -(ax+by) = a(-x)+b(-y)$。因为 $-x, -y$ 仍是整数，所以 $-h$ 也在 $H$ 中。
   • 因此，$H$ 是 $\mathbb{Z}$ 的一个子群。
   • 作者还提到，这个 $H$ 就是由 $a,b$ 生成的子群 $\langle a,b \rangle$。

第三步：利用$\mathbb{Z}$子群的性质

• 我们在命题1.1.5中证明了：$\mathbb{Z}$ 的每个子群都是循环的。
• 因此，$H$ 也必须是一个循环群。这意味着存在一个整数 $d$ 使得 $H = \langle d \rangle$。
• $\langle d \rangle$ 就是所有 $d$ 的倍数的集合。
• 所以，我们得出了一个惊人的结论：$a,b$ 的所有线性组合的集合，恰好是某个整数 $d$ 的所有倍数的集合。
• $H = \{ax+by\} = \{kd \mid k \in \mathbb{Z}\}$。
• 因为 $a,b$ 不全为0，所以 $H$ 不是 $\{0\}$ 子群。因此我们可以取生成元 $d$ 为正数，即 $d \in \mathbb{N}$。

第四步：证明这个生成元d就是GCD

• 我们来验证这个正生成元 $d$ 是否满足GCD的定义(1.2.1)。

1. 证明d是公约数:
   • 因为 $a \in H$ ($a=a\cdot 1+b\cdot 0$)，且 $H=\langle d \rangle$，所以 $a$ 必须是 $d$ 的倍数，即 $d \mid a$。
   • 同理，$b \in H$ ($b=a\cdot 0+b\cdot 1$)，所以 $d \mid b$。
   • 因此，$d$ 是 $a$ 和 $b$ 的一个公约数。
2. 证明d是“最大”的:
   • 设 $e$ 是 $a$ 和 $b$ 的任意一个公约数，即 $e \mid a$ 且 $e \mid b$。
   • 我们要证明 $e \mid d$。
   • 因为 $d$ 本身是 $H$ 的一个元素（它是生成元），所以 $d$ 必然可以写成 $a,b$ 的线性组合形式：$d = ax_0 + by_0$ (对于某组特定的整数 $x_0, y_0$)。
   • 根据整除的线性组合性质(3)，如果 $e$ 能整除 $a$ 和 $b$，那么 $e$ 也能整除它们的任何线性组合。
   • 因此，$e \mid (ax_0 + by_0)$，即 $e \mid d$。
   • 结论：这个正生成元 $d$ 完美地满足了最大公约数的两个条件。所以 $d = \operatorname{gcd}(a,b)$。

第五步：完成对定理三个部分的证明

• (i) 存在性: 我们已经通过构造 $H$ 并找到其正生成元 $d$，成功地找到了一个满足GCD定义的数，因此GCD存在。唯一性由引理保证。
• (ii) 线性组合表示: 在第四步中，我们已经推导出 $d$ 作为 $H$ 的元素，可以表示为 $d=an+bm$ 的形式。
• (iii) 丢番图方程: 我们已经建立了等式 $H = \langle d \rangle$。
• $ax+by=c$ 有整数解 $\iff c$ 是 $a,b$ 的一个线性组合 $\iff c \in H$。
• 另一方面，$d \mid c \iff c$ 是 $d$ 的一个倍数 $\iff c \in \langle d \rangle$。
• 因为 $H = \langle d \rangle$，所以 $c \in H \iff c \in \langle d \rangle$。
• 综上，$ax+by=c$ 有解 $\iff d \mid c$。

这个备注将裴蜀定理证明中的核心思想进行了抽象和推广。

• 从 $\mathbb{Z}$ 推广到任意阿贝尔群 G:
• 证明裴蜀定理时，我们考虑的是整数加法群 $\mathbb{Z}$。
• 这里，我们将这个思想应用到任何一个阿贝尔群（即运算满足交换律的群）$G$ 上。
• 为了与 $\mathbb{Z}$ 的运算保持形式上的一致，我们暂时将群 $G$ 的运算写成加法“+”。

• 从两个元素推广到 k 个元素:
• 证明裴蜀定理时，我们考虑的是由两个元素 $a,b$ 生成的子群 $H=\{ax+by\}$。
• 这里，我们推广到由 $k$ 个元素 $g_1, \ldots, g_k$ 生成的子群。

• 集合的定义:
• 集合 $\langle g_1, \ldots, g_k \rangle$ 被定义为 $g_1, \ldots, g_k$ 的所有整数线性组合的集合。
• 形式为 $n_1 g_1 + \ldots + n_k g_k$，其中系数 $n_i$ 是整数。
• 这里的 $n_i g_i$ 是群论中的标量乘法，表示将元素 $g_i$ 与自身相加 $n_i$ 次（如果 $n_i$ 是负数，则是将逆元相加 $|n_i|$ 次）。

• 结论:

1. 这个集合是一个子群: 我们可以像证明裴蜀定理时那样，验证它对群运算封闭、包含单位元、包含逆元。
2. 包含 $g_1, \ldots, g_k$: 例如，取 $n_1=1, n_2=\ldots=n_k=0$，就得到 $1 \cdot g_1 = g_1$，所以 $g_1$ 在集合中。同理，所有 $g_i$ 都在集合中。
3. 是最小的此类子群: “最小”是指在集合包含意义下的最小。任何其他包含 $g_1, \ldots, g_k$ 的子群 $H'$，都必然包含它们的线性组合，因此必然包含整个 $\langle g_1, \ldots, g_k \rangle$ 集合。所以 $\langle g_1, \ldots, g_k \rangle$ 是所有包含这些元素的子群中最小的那一个。

这部分定义了互素 (coprime 或 relatively prime) 这个非常重要的数论概念。

• 核心定义: 两个不全为0的整数 $a,b$ 是互素的，当且仅当它们的最大公约数是1。
• 等价描述:
• “如果一个整数$e$同时整除$a$和$b$...”：这意味着 $e$ 是 $a$ 和 $b$ 的一个公约数。
• “...那么 $e$ 整除 $1$”：根据GCD的定义(1.2.1)，所有公约数都必须整除GCD。如果GCD是1，那么所有公约数都必须整除1。
• “...或者等价地 $e = \pm 1$”：在整数中，能整除1的数只有1和-1。
• 所以，互素的等价说法就是：两个整数除了 $\pm 1$ 之外，没有其他的公共因子。

这个引理是裴蜀定理在互素情况下的一个直接推论，也是互素最重要的一个判定性质。

• $\Longleftrightarrow$: 表示这是一个当且仅当的等价关系。

证明 "$\boldsymbol{\Rightarrow}$" (如果 $a,b$ 互素，那么 $ax+by=1$ 有解)

• 假设 $a,b$ 互素。
• 根据互素的定义，$\operatorname{gcd}(a,b)=1$。
• 根据裴蜀定理 (定理1.2.4(ii))，最大公约数总可以被表示为 $a,b$ 的线性组合。
• 将 $d=\operatorname{gcd}(a,b)=1$ 代入裴蜀等式 $d=ax+by$，我们直接得到 $1=ax+by$。
• 这证明了存在这样的整数 $x,y$。

证明 "$\boldsymbol{\Leftarrow}$" (如果 $ax+by=1$ 有解，那么 $a,b$ 互素)

• 假设存在整数 $x,y$ 使得 $ax+by=1$。
• 设 $d=\operatorname{gcd}(a,b)$。
• 根据GCD的定义，$d$ 是 $a,b$ 的公约数，所以 $d \mid a$ 且 $d \mid b$。
• 根据整除的线性组合性质(3)，如果 $d$ 整除 $a$ 和 $b$，那么它也必须整除它们的任何线性组合。
• 因此，$d \mid (ax+by)$。
• 既然我们假设了 $ax+by=1$，那么就意味着 $d \mid 1$。
• 一个能整除1的正整数（GCD定义要求为正）只有1。
• 所以 $d=1$。
• 根据互素的定义，$\operatorname{gcd}(a,b)=1$ 意味着 $a,b$ 互素。

这个命题是数论中一个极其重要的结果，通常被称为欧几里得引理 (Euclid's Lemma)。它描述了互素关系下的一个关键的“整除传递”性质。

• 前提:

1. $a, b$ 互素，即 $\operatorname{gcd}(a,b)=1$。
2. $a$ 整除 $b$ 和 $c$ 的乘积，即 $a \mid bc$。
   • 结论: $a$ 必须整除 $c$。

• 直观理解: 如果 $a$ 整除 $bc$，通常我们只能说 $a$ 的因子“分散”在 $b$ 和 $c$ 中。但如果 $a$ 和 $b$ 互素，意味着 $a$ 和 $b$ 没有任何共同的素因子。那么构成 $a$ 的那些素因子，就必然全部都在 $c$ 的素因子中。因此，$a$ 必然能整除 $c$。

证明思路:

这个证明巧妙地运用了引理1.2.7。

第一步：利用互素性质

• 因为 $a,b$ 互素，根据引理1.2.7，存在整数 $x,y$ 使得 $ax+by=1$。

第二步：创造出我们想证明的目标 $c$

• 我们想证明 $a \mid c$。一个直接的方法是把 $c$ 表示成 $a$ 的倍数。
• 我们手上有一个关于1的等式，为了得到关于 $c$ 的等式，最自然的操作是将等式两边同时乘以 $c$。
• $c(ax+by) = c \cdot 1 \implies acx + bcy = c$。

第三步：利用另一个前提 $a \mid bc$

• 我们来分析 $acx + bcy = c$ 这个等式的左边两项。
• 第一项 $acx$：它明显包含因子 $a$，所以 $a \mid acx$。
• 第二项 $bcy$：我们可以把它看成 $(bc)y$。根据前提，我们知道 $a \mid bc$。所以 $a$ 也必然整除 $bc$ 的整数倍，即 $a \mid (bc)y$。
• 利用整除的线性组合性质:
• 如果 $a$ 整除两项，那么它也必然整除这两项的和。
• 所以，$a \mid (acx + bcy)$。

第四步：得出结论

• 因为 $acx+bcy = c$，所以我们得出 $a \mid c$。
• 证明完毕。

这部分给出了素数 (prime number) 的标准定义。

• $p \in \mathbb{N}$: 素数被定义为自然数（正整数）。
• $p>1$: 1被明确排除在素数之外。这是现代数学的约定。
• 并且对于所有的$n \in \mathbb{N}$，如果$n \mid p$那么$n=1$或$n=p$: 这是素数的核心性质。它的正因子 (divisors) 只有1和它本身。换句话说，它不能被分解为比它自己小的两个正整数的乘积。

为什么1不是素数？

如果1是素数，那么算术基本定理（任何大于1的整数都可以唯一地分解为素数的乘积）就会出问题。例如，$6 = 2 \times 3$，也可以写成 $6 = 1 \times 2 \times 3$，或者 $6 = 1^2 \times 2 \times 3$，分解方式就不唯一了。将1排除在外，保证了唯一性。

这个引理描述了素数与任意整数之间关系的一个基本二分法。

证明思路:

• 考虑 $p$ 和 $n$ 的最大公约数，设为 $d = \operatorname{gcd}(p, n)$。
• 根据GCD的定义，$d$ 是一个正整数，并且 $d$ 必须整除 $p$ ($d \mid p$)。
• 因为 $p$ 是一个素数，根据素数的定义，它的正因子只有1和 $p$。
• 所以， $d$ 的值只有两种可能：$d=1$ 或 $d=p$。
• 情况一: $d=1$
• 如果 $d = \operatorname{gcd}(p,n) = 1$，那么根据互素的定义， $p$ 和 $n$ 互素。
• 情况二: $d=p$
• 如果 $d = \operatorname{gcd}(p,n) = p$，那么根据GCD的定义，$d$ 必须也整除 $n$，即 $p \mid n$。
• 结论: 这两种情况涵盖了所有可能性，并且是互斥的（如果 $p \mid n$，那么 $\operatorname{gcd}(p,n)=p$，不可能等于1，除非 $p=1$，但素数定义排除了p=1）。所以，$p$ 和 $n$ 的关系必然是这两种之一。

这是欧几里得引理的一个特例，也是其最重要的应用。它通常也被直接称为欧几里得引理。

证明思路:

这个证明完美地结合了命题1.2.8和引理1.2.10。

• 前提: $p$ 是素数，且 $p \mid ab$。
• 目标: 证明 $p \mid a$ 或 $p \mid b$。
• 使用引理1.2.10: 我们考虑素数 $p$ 和整数 $a$ 之间的关系。根据引理1.2.10，只有两种可能：

1. $p \mid a$。
2. $p$ 和 $a$ 互素。
   • 分情况讨论:
   • 情况一: 如果 $p \mid a$:
   • 那么我们的结论 "$p \mid a$ 或 $p \mid b$" 已经成立了。证明结束。
   • 情况二: 如果 $p$ 和 $a$ 互素:
   • 现在我们有了两个条件：
   • (1) $p$ 和 $a$ 互素。
   • (2) $p \mid ab$ (这是题目给的前提)。
   • 这完全符合命题1.2.8 (欧几里得引理) 的应用场景：把这里的 $p$ 看作那里的 $a$，这里的 $a$ 看作那里的 $b$，这里的 $b$ 看作那里的 $c$。
   • 命题1.2.8说：如果一个数整除一个乘积，且与其中一个因子互素，那么它必须整除另一个因子。
   • 应用到这里就是：如果 $p$ 整除 $ab$，且 $p$ 与 $a$ 互素，那么 $p$ 必须整除 $b$。
   • 这样，我们也得到了结论 "$p \mid b$"。
   • 总结: 在任何情况下，结论 "$p \mid a$ 或 $p \mid b$" 都成立。证明完毕。

这个推论是将推论1.2.11从两个因子的情况推广到任意多个因子的情况。

证明思路:

这个证明使用数学归纳法。

• 基础步骤 (k=2):
• 当 $k=2$ 时，命题是“如果 $p \mid a_1 a_2$，那么 $p \mid a_1$ 或 $p \mid a_2$”。
• 这正是推论1.2.11的内容，我们已经证明了它。

• 归纳假设 (假设k-1成立):
• 假设对于 $k-1$ 个因子的乘积，命题成立。即：如果 $p \mid a_1 \cdots a_{k-1}$，那么存在某个 $j \in \{1, \ldots, k-1\}$ 使得 $p \mid a_j$。

• 归纳步骤 (证明k成立):
• 我们要证明：如果 $p \mid a_1 \cdots a_k$，那么存在某个 $i \in \{1, \ldots, k\}$ 使得 $p \mid a_i$。
• 我们可以把乘积 $a_1 \cdots a_k$ 看成两个“大”因子的乘积：
• 令 $A = a_1 \cdots a_{k-1}$
• 令 $B = a_k$
• 那么前提变成了 $p \mid A \cdot B$。
• 根据基础步骤 (k=2的情况)，我们知道：$p \mid A$ 或 $p \mid B$。
• 情况一: 如果 $p \mid B$:
• $B=a_k$，所以 $p \mid a_k$。结论成立 (取 $i=k$)。
• 情况二: 如果 $p \mid A$:
• $A = a_1 \cdots a_{k-1}$。所以我们有 $p \mid a_1 \cdots a_{k-1}$。
• 现在我们可以应用归纳假设了。根据归纳假设，必然存在一个 $i \in \{1, \ldots, k-1\}$ 使得 $p \mid a_i$。结论也成立。
• 结论: 无论哪种情况，我们都找到了一个 $i$ 使得 $p \mid a_i$。因此，通过数学归纳法，命题对所有 $k \ge 2$ 成立。

这是整个数论乃至整个数学最重要的基石之一。它包含两个独立的部分：存在性和唯一性。

• 存在性: 任何大于1的整数，总可以被写成若干个素数的乘积。
• 唯一性: 这种分解方式是唯一的，不考虑因子的顺序。

证明思路:

存在性证明 (使用强归纳法)

• 基础步骤 (n=2): 2本身是素数，分解式就是2。成立。
• 归纳假设: 假设对于所有小于 $n$ 的整数 $k$ ($1<k<n$)，它们都可以被分解为素数的乘积。
• 归纳步骤 (证明n):
• 情况一: 如果 $n$ 本身是素数: 那么它的分解式就是 $n$。成立。
• 情况二: 如果 $n$ 是合数: 那么 $n$ 可以被分解为两个更小的整数的乘积，即 $n = a \cdot b$，其中 $1 < a \le b < n$。
• 根据归纳假设，$a$ 和 $b$ 都可以被分解为素数的乘积。

$a = p_1 \cdots p_k$

$b = q_1 \cdots q_m$

• 那么 $n = ab = (p_1 \cdots p_k)(q_1 \cdots q_m)$。这也是一个素数的乘积。
• 结论: 在任何情况下，$n$ 都可以被分解为素数的乘积。存在性证明完毕。

唯一性证明 (关键部分，使用推论1.2.12)

• 假设: 假设同一个整数 $n$ 有两种不同的素数分解：

$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$

其中所有的 $p_i$ 和 $q_j$ 都是素数。

• 目标: 证明 $r=s$，并且 $p$ 集合和 $q$ 集合在重新排序后是完全一样的。
• 使用推论1.2.12:
• 考虑第一个等式 $p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$。
• 左边是 $p_1$ 的倍数，所以 $p_1$ 必然整除右边的乘积 $q_1 \cdots q_s$。
• 根据推论1.2.12，如果一个素数整除一个乘积，它必须整除其中一个因子。
• 所以，存在某个 $j$，使得 $p_1 \mid q_j$。
• 因为 $q_j$ 本身也是一个素数，它的正因子只有1和 $q_j$。而 $p_1 > 1$，所以唯一的可能性是 $p_1 = q_j$。
• 消去与归纳:
• 我们找到了一个匹配！$p_1$ 必然等于某个 $q_j$。不失一般性，我们可以重新排列 $q$ 的顺序，使得 $q_1 = p_1$。
• 现在等式变成 $p_1 p_2 \cdots p_r = p_1 q_2 \cdots q_s$。
• 因为 $p_1 \neq 0$，我们可以在等式两边消去 $p_1$，得到：

$p_2 \cdots p_r = q_2 \cdots q_s$

• 重复此过程:
• 我们可以对 $p_2$ 重复同样的论证，证明它必然等于剩下的某个 $q_j$。然后消去它们。
• 这个过程可以一直进行下去。
• 如果 $r < s$，那么我们会先把左边的 $p$ 全部消完，得到 $1 = q_{r+1} \cdots q_s$。这是不可能的，因为素数都大于1。
• 如果 $s < r$，也会得到类似矛盾。
• 因此，因子个数必须相等，即 $r=s$。
• 并且在这个过程中，我们已经将每一步的 $p_i$ 与一个 $q_j$ 配对并消去。
• 这就证明了两个分解式在重新排序后是完全一样的。唯一性证明完毕。

这个备注给出了算术基本定理的一个更规范、更常用的表示形式，称为标准分解式或典范分解式 (canonical representation)。

• $n=p_{1} \cdots p_{r}$: 这是定理中给出的基本形式，允许素因子重复出现，例如 $12=2 \times 2 \times 3$。
• $n=p_{1}^{n_{1}} \cdots p_{r}^{n_{r}}$: 这是标准形式。它将相同的素因子合并成幂的形式。
• $12 = 2^2 \times 3^1$。
• $p_{1}<\cdots<p_{r}$: 为了保证绝对的唯一性（连顺序都唯一），我们约定将素数底数从小到大排列。
• $n_{i}$是正整数: 指数 $n_i$ (也称为素因子 $p_i$ 的重数 multiplicity) 必须是正整数。

从基本形式到标准形式:

通过收集所有相同的素因子并按升序排列，任何一个素数分解式都可以被转化为唯一的标准分解式。

本节将介绍一种古老而又极其高效的算法，用于计算两个整数的最大公约数。这个算法最早出现在欧几里得的《几何原本》中，因此得名。与需要进行困难的素因数分解的方法不同，该算法只使用简单的带余除法。

这部分详细描述了欧几里得算法（又称辗转相除法）的步骤。

算法核心思想:

基于一个关键引理：$\operatorname{gcd}(a, b) = \operatorname{gcd}(b, r)$，其中 $r$ 是 $a$ 除以 $b$ 的余数。

为什么这个引理成立？

设 $d$ 是 $a,b$ 的一个公约数，则 $d \mid a$ 且 $d \mid b$。因为 $r = a - bq$，所以 $d$ 也必然整除 $r$。因此 $d$ 也是 $b, r$ 的一个公约数。

反之，设 $d'$ 是 $b,r$ 的一个公约数，则 $d' \mid b$ 且 $d' \mid r$。因为 $a = bq+r$，所以 $d'$ 也必然整除 $a$。因此 $d'$ 也是 $a,b$ 的一个公约数。

结论：$a,b$ 的公约数集合与 $b,r$ 的公约数集合完全相同。因此，它们的最大公约数也必然相同。

算法步骤:

1. 输入: 两个正整数 $a,b$ (不妨设 $a \ge b$)。
2. 第一步: 做带余除法， $a = b q_1 + r_1$，其中 $0 \le r_1 < b$。
3. 判断: 如果余数 $r_1=0$，那么除数 $b$ 就是最大公约数。算法结束。
4. 迭代: 如果余数 $r_1 \neq 0$，那么问题 $\operatorname{gcd}(a,b)$ 就转化为了一个规模更小的相同问题 $\operatorname{gcd}(b, r_1)$。将 $(a,b)$ 更新为 $(b, r_1)$，然后回到第2步。
5. 终止: 这个过程会不断产生一个严格递减的非负余数序列 $b > r_1 > r_2 > r_3 > \ldots \ge 0$。因为这个序列不能无限递减，所以最终必然会出现一个余数为0的情况。当 $r_{n+1}=0$ 时，算法终止，此时的除数，也就是前一个余数 $r_n$，就是所求的最大公约数。

线性组合的保持:

作者在描述中特别指出，每一步产生的余数，始终都可以表示为原始数 $a, b$ 的线性组合。

• $r_1 = a - bq_1 = a(1) + b(-q_1)$。
• $r_2 = b - r_1 q_2 = b - (a - bq_1)q_2 = a(-q_2) + b(1+q_1q_2)$。
• 依此类推，通过归纳法可以证明，所有余数 $r_i$ 都是 $a,b$ 的线性组合。
• 最终得到的GCD（最后一个非零余数 $r_n$），也必然是 $a,b$ 的一个线性组合。这为裴蜀定理提供了一个构造性证明。